package com.sourcetrip.algorithm.sort.bubble;

import com.sourcetrip.algorithm.abs.AbstractSort;

/**
 * @author: xiaomi
 * @date: 2020/12/27
 * @description: 冒泡排序的改进版本
 * 分析:
 * 1.当进行一次遍历以后，如果没有发生过交换，说明后面已经是有序了。此时就可以退出循环。
 * 反思：
 * 其实优化的情况很难遇到，因为只有当某次遍历时发现完全有序才能体现优化的价值！这种情况是很少的！
 */
public class BubbleSortV1 extends AbstractSort {


    @Override
    protected int[] sortArr(int[] arr) {

        boolean haveSwapped = false;
        for (int j = 0, end = arr.length - 1; j < arr.length; j++) {
            haveSwapped = false;
            for (int i = 1; i <= end; i++) {
                if (arr[i - 1] > arr[i]) {
                    swap(arr, i - 1, i);
                    //flag
                    haveSwapped = true;
                }
            }
            //如果本轮没有进行过交换，说明后面已经有序
            //由于从 索引为0 开始进行比较，所以此时已经完全有序
            if (!haveSwapped) {
                break;
            }
            end--;
        }
        return arr;
    }
}
